from functools import cache,lru_cache


class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        n1, n2, m = len(s1), len(s2), len(s3)
        # 长度不匹配，直接返回 False
        if m != n1 + n2:
            return False
        # 满足条件就记忆化搜索
        @cache
        def dfs(i, j, z):
            # 当 i 和 j 都遍历完，且 z 也遍历完，说明 s3 可以由 s1 和 s2 交错组成
            if i == n1 and j == n2 and z == m:
                return True
            # 尝试从 s1 中取字符
            can_use_s1 = i < n1 and s1[i] == s3[z]
            # 尝试从 s2 中取字符
            can_use_s2 = j < n2 and s2[j] == s3[z]
            # 只要有一种情况能得到正确结果，就返回 True
            # 不会有不选的情况，因为 s1+s2的长度 == len(s3) ,只会存在，选i，还是选j的情况
            return (can_use_s1 and dfs(i + 1, j, z + 1)) or (can_use_s2 and dfs(i, j + 1, z + 1))

        return dfs(0, 0, 0)

# 动态规划
class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        n1, n2, m = len(s1), len(s2), len(s3)
        if m != n1 + n2:
            return False
        # 创建一个二维数组 dp，dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符能否交错组成 s3 的前 i + j 个字符
        dp = [[False] * (n2 + 1) for _ in range(n1 + 1)]
        # 初始化边界条件
        dp[0][0] = True
        # 处理 s2 为空的情况
        for i in range(1, n1 + 1):
            dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]
        # 处理 s1 为空的情况
        for j in range(1, n2 + 1):
            dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]
        # 填充 dp 数组
        for i in range(1, n1 + 1):
            for j in range(1, n2 + 1):
                dp[i][j] = (dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]) or (dp[i][j - 1] and s2[j - 1] == s3[i + j - 1])
        return dp[n1][n2]

